// 无重复字符的最长子串
// 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  let arr = [], max = 0 
  for (let i = 0; i < s.length; i++) {
    let index = arr.indexOf(s[i]) 

    if (index !== -1) {
      arr.splice(0, index + 1)
    }

    arr.push(s.charAt(i))

    max = Math.max(arr.length, max)
  }

  return max
}



// 二叉树先序遍历
function preOrder(root) {
 if (!root) {
  return
 }
 console.log('当前遍历的结点值是：', root.val)
 preOrder(root.left)
 preOrder(root.right)
}
// 二叉树中序遍历
function centerOrder(root) {
  if (!root) {
    return
  }
  preOrder(root.left)
  console.log('当前遍历的结点值是：', root.val)
  preOrder(root.right)
}

// 二叉树后序遍历
function afterOrder(root) {
 if (!root) {
  return
 }
 preOrder(root.left)
 preOrder(root.right)
 console.log('当前遍历的结点值是：', root.val)
}


// 1. Map 的妙用----两数求和问题
const nums = [2, 7, 11, 15], target = 9
const twoSum = (nums, target) => {
  const diffs = {}
  for (let i = 0; i < nums.length; i++) {
    if (diffs[target - nums[i]] !== undefined) {
      return [diffs[target - nums[i]], i]
    }
    diffs[nums[i]] = i
  }
}

// 2. 强大的双指针法----合并两个有序数组
const nums1 = [1, 2, 3, 0, 0, 0], m = 3
const nums2 = [2, 5, 6], n = 3
const merge = (nums1, m, nums2, n) => {
  let i = m - 1; j = n - 1, k = m + n - 1
  while(i >= 0 && j >= 0) {
    if (nums1[i] >= nums2[j]) {
      nums1[k] = nums1[i]
      i--
      k--
    } else {
      nums1[k] = nums2[j]
      j--
      k--
    }
  }

  while(j >= 0) {
    nums1[k] = nums2[j]
    j--
    k--
  }
}

// 3. 对撞指针----三数求和问题
const nums3 = [-1, 0, 1, 2, -1, -4]
// [-4, -1, -1, 0, 1, 2]
const threeSum = (nums) => {
  nums.sort((a, b) => a - b)
  let res = []

  for(let i = 0; i < nums.length - 2; i++) {
    let j = i + 1, k = nums.length - 1 
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }
    while(j < k) {
      if (nums[i] + nums[j] + nums[k] < 0) {
        j++
        while(j < k && nums[j] === nums[j - 1]) {
          j++
        }
      } else if (nums[i] + nums[j] + nums[k] > 0) {
        k-- 
        while(j < k && nums[k] === nums[k + 1]) {
          k--
        }
      } else {
        res.push([nums[i], nums[j], nums[k]])
        j++
        while(j < k && nums[j] === nums[j - 1]) {
          j++
        }
        k-- 
        while(j < k && nums[k] === nums[k + 1]) {
          k--
        }
      }
    }
  }
  return res
}

// 4. 翻转字符串
const str = 'juejin'
str.split('').reverse().join('')
// 5. 判断一个字符串是否是回文字符串
// 方法1 翻转字符串
function isPalindrome(str) {
  let reverseStr = str.split('').reverse().join('')
  return str === reverseStr
}
// 方法2 结合对称性来做判断
function isPalindrome(str) {
 for(let i = 0; i < str.length/2;i++) {
  if (str[i] !== str[str.length - 1 - i]) {
    return false
  }
 }

 return true
}

// 6.回文字符串的衍生问题， 给定一个非空字符串s, 最多删除一个字符。判断是否能成为回文字符串
function validPalindrome(s) {
  const len = s.length 
  let i = 0, j = len - 1 

  while(i < j && s[i] === s[j]) {
    i++ 
    j--
  }
  if (isPalindrome(i + 1, j)) {
    return true
  }

  if (isPalindrome(i, j - 1)) {
    return true
  }

  function isPalindrome(st, ed) {
    while(st < ed) {
      if (s[st] !== s[ed]) {
        return false
      }
      st++
      ed--
    }
    return true
  }

  return false
}

// 7. 字符串匹配问题----正则表达式初相见
/**
 * 构造函数
 */
function WordDictionary() {
  this.words = {}
}

WordDictionary.prototype.addWord = (word) => {
  if (this.words[word.length]) {
    this.words[word.length].push(word)
  } else {
    this.words[word.length] = [word]
  }
}

WordDictionary.prototype.searchWord = (word) => {
 if (!this.words[word.length]) {
  return false
 }
 const len = word.length 
 if (!word.includes('.')) {
  return this.words[len].includes(word)
 }

 const reg = new RegExp(word)

 return this.words[len].some(item => {
  return reg.test(item)
 })
}


// 8.正则表达式更进一步----字符串与数字之间的转换问题
const myAtoi = (s) => {
  const reg = /\s*([-\+]?[0-9]*).*/
  const groups = str.match(reg)
  const max = Math.pow(2, 31) - 1
  const min = -max - 1
  let targetNum = 0 
  if (groups) {
    targetNum = +groups[1]
    if (isNaN(targetNum)) {
      targetNum = 0
    }
  }
  if (targetNum > max) {
    return max
  } else if (targetNum < min) {
    return min
  }
  return targetNum
}

// 9. 链表 
// 创建链表结点，需要使用构造函数
function ListNode(val) {
  this.val = val 
  this.next = null
}
// 10. 链表的合并
// 真题描述：将两个有序链表合并为一个新的有序链表并返回。
// 新链表是通过拼接给定的两个链表的所有结点组成的。 
// 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
let l1 = {
  val: 1,
  next: {
    val: 2, 
    next: {
      val: 4,
      next: null
    }
  }
}
let l2 = {
  val: 1, 
  next: {
    val: 3,
    next: {
      val: 4,
      next: null
    }
  }
}


// 11. 链表结点的删除
// 真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
// 示例 1:
// 输入: 1->1->2
// 输出: 1->2
// 示例 2:
// 输入: 1->1->2->3->3
// 输出: 1->2->3
const deleteDuplicates = head => {
 
}


// 12. 删除问题的延伸----dummy结点登场
// 真题描述：给定一个排序链表，删除所有含有重复数字的结点，
// 只保留原始链表中 没有重复出现的数字。
// 示例 1:
// 输入: 1->2->3->3->4->4->5
// 输出: 1->2->5
// 示例 2:
// 输入: 1->1->1->2->3
// 输出: 2->3



// 13.快慢指针----删除链表的倒数第N个结点
// 真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
// 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2.
// 当删除了倒数第二个结点后，链表变为 1->2->3->5.
// 说明： 给定的 n 保证是有效的。



// 14. 多指针法----链表的反转
// 真题描述：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
// 示例:
// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL


// 15. 局部反转一个链表
// 真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
// 说明: 1 ≤ m ≤ n ≤ 链表长度。
// 示例:
// 输入: 1->2->3->4->5->NULL, m = 2, n = 4
// 输出: 1->4->3->2->5->NULL



// 16. 环形链表基本问题——如何判断链表是否成环？
// 真题描述：给定一个链表，判断链表中是否有环。
// 示例 1：
// 输入：[3,2,0,4]（链表结构如下图） 输出：true
// 解释：链表中存在一个环



// 快慢指针法


// 哈希表



// 17. 环形链表衍生问题——定位环的起点
// 真题描述：给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
